#include "TextFPLocationBDB.h"

// The two comparison call-back functions "compareIntValues" & "compareIntKeys" are 
// needed to convert the byte strings stored in the BerkelyDB database into numeric 
// values to do the comparisons properly.  If these are not supplied,
// Berkely DB uses a default lexical comparison; which is not correct when 
// values are stored in little edian format like on Windows machines. 
int compareData(Db *dbp, const Dbt *pValuea, const Dbt *pValueb)
{
    FilePosition_t iValuea;  // data value supplied by the application
    FilePosition_t iValueb;  // data value stored in the database

    // Returns:
    // < 0 if a < b
    // = 0 if a = b
    // > 0 if a > b
    memcpy(&iValuea, pValuea->get_data(), sizeof(FilePosition_t));
    memcpy(&iValueb, pValueb->get_data(), sizeof(FilePosition_t));
    if (iValuea < iValueb)
        return -1;
    else if (iValuea == iValueb)
        return 0;
    else
        return 1;

//    return (iValuea - iValueb);
}

int compareKeys(Db *dbp, const Dbt *pKeya, const Dbt *pKeyb)
{
    HashValue_t iKeya;  // key value supplied by the application
    HashValue_t iKeyb;  // key value stored in the database

    // Returns:
    // < 0 if a < b
    // = 0 if a = b
    // > 0 if a > b
    memcpy(&iKeya, pKeya->get_data(), sizeof(HashValue_t));
    memcpy(&iKeyb, pKeyb->get_data(), sizeof(HashValue_t));
    if (iKeya < iKeyb)
        return -1;
    else if (iKeya == iKeyb)
        return 0;
    else
        return 1;
//    return (iKeya - iKeyb);
}

// Class constructor. Requires a path to database location and a database name
TextFPLocationBDB::TextFPLocationBDB(std::string &path, std::string &name, bool isWrite)
    : dbh_(NULL, 0),               // Instantiate Db object
      dbPath_(path),
      dbName_(name),
      dbFileName_(dbPath_ + dbName_)
{
    try
    {
        std::string::size_type offPos = dbName_.find_last_of('.');
        if (offPos == std::string::npos)
            throw "No database extension; database name must have an \'.extension\' suffix.";
        dbExtension_ = dbName_.substr(offPos, (dbName_.length() - offPos));
        //// delete database to start fresh.
        //std::string delFiles = dbPath_ + '*' + dbExtension_;
        //system(delFiles.c_str());

        isWrite_ = isWrite;
        // Redirect debugging information to std::cerr
        dbh_.set_error_stream(&std::cerr);

        if (isWrite_)
        {
            cFlags_ = (DB_CREATE);
        }
        else
        {
            cFlags_ = (DB_RDONLY);
        }

        dbh_.set_flags(DB_DUPSORT);
        dbh_.set_bt_compare(compareKeys) ;
        dbh_.set_dup_compare(compareData) ;
//-EXP-adjust page and cache size.
//    -The default values forced the time per Mb to keep increasing upt to about 150 secs/Mb;which was too long
//    -Now we are in the range of 5-10 secs/Mb which is approaching acceptable levels
//        dbh_.set_pagesize(65536);
//        dbh_.set_pagesize(32768);
//        dbh_.set_pagesize(16384);
//        dbh_.set_pagesize(8192);
//        dbh_.set_pagesize(4096);
//        dbh_.set_pagesize(2048);
        dbh_.set_pagesize(1024);
//        dbh_.set_cachesize(1,0,6);
//        dbh_.set_cachesize(2,0,10);
//        dbh_.set_cachesize(3,0,15); //MALLOC not enough space....
        dbh_.set_cachesize(3,0,20);

        // Open the database
        dbh_.open(NULL, dbFileName_.c_str(), NULL, DB_BTREE, cFlags_, 0);
        // open a cursor for our database
        dbh_.cursor(NULL, &pdbc_, 0);

        //clear the database value variables
        memset(&dbValue_, 0, sizeof(dbValue_));
        memset(&dbKey_, 0, sizeof(dbKey_));
        // declare the database value types
        dbKey_.set_size(sizeof(HashValue_t));
        dbValue_.set_size(sizeof(FilePosition_t));
        dbKey_.set_flags(DB_DBT_USERMEM);
        dbValue_.set_flags(DB_DBT_USERMEM);

    }
    // DbException is not a subclass of std::exception, so we
    // need to catch them both.
    catch(DbException &e)
    {
        std::cerr << "Error opening database: " << dbFileName_ << "\n";
        std::cerr << e.what() << std::endl;
    }
    catch(std::exception &e)
    {
        std::cerr << "OS Error opening database: " << dbFileName_ << "\n";
        std::cerr << e.what() << std::endl;
    }
}

// Private member used to close a database. Called from the class
// destructor.
void TextFPLocationBDB::close()
{
    // Close the db
    try
    {
        pdbc_->close();
        dbh_.close(0);
        std::cout << "Database " << dbFileName_
                  << " is closed." << std::endl;
    }
    catch(DbException &e)
    {
        std::cerr << "Error closing database: " << dbFileName_ << "\n";
        std::cerr << e.what() << std::endl;
    }
    catch(std::exception &e)
    {
        std::cerr << "Error closing database: " << dbFileName_ << "\n";
        std::cerr << e.what() << std::endl;
    }
}

int TextFPLocationBDB::putBDBRec(HashValue_t pKey, FilePosition_t pValue)
{
   dbKey_.set_data((void*)(&pKey));
   dbValue_.set_data((void*)(&pValue));
   
   return dbh_.put(NULL, &dbKey_, &dbValue_, DB_NODUPDATA);
   
    /* this is the original program.

    Dbt localKey;
    Dbt localData;

    //clear the database value variables
    memset(&localData, 0, sizeof(localData));
    memset(&localKey, 0, sizeof(localKey));
    // declare the database value types
    localKey.set_size(sizeof(HashValue_t));
    localData.set_size(sizeof(FilePosition_t));

   localKey.set_data((void*)(&pKey));
   localData.set_data((void*)(&pValue));
   
   return dbh_.put(NULL, &localKey, &localData, DB_NODUPDATA);
*/
}

// this function finds the locations for a single key and puts them into pVector
int TextFPLocationBDB::getLocsForFP(HashValue_t pKey, std::vector<FilePosition_t> &pLocationVector)
{
    // create variable to store location data
    FilePosition_t data_value;

    // clear the memory for the location data
    memset(&data_value,0,sizeof(FilePosition_t));
    memset(&dbValue_, 0, sizeof(dbValue_));

    //set the key to find
    dbKey_.set_data((void*)(&pKey));
    
    int ret;

    // set the flag so the cursor's get will find the first key that is
    // equal to the 'pKey' parameter
    u_int32_t getFlag = DB_SET;

    //find the first value of the key and loop through the values
    while ((ret = pdbc_->get(&dbKey_, &dbValue_, getFlag)) == 0)
    {
        memcpy(&data_value,dbValue_.get_data(),sizeof(FilePosition_t));
        // add this location to our list
        pLocationVector.push_back(data_value);
        // reset the flag so the cursor's get will find the next duplicate key
        getFlag = DB_NEXT_DUP;
    }

    return 0;
}

// this function finds the locations for a range of fingerprints by searching the database 
// for keys between the range and calling "getLocsForFP()" for each fingerprint
int TextFPLocationBDB::getLocsForFPRange(HashValue_t fromKey, HashValue_t toKey, std::vector<FilePosition_t> &pLocationVector)
{
    // we need to use local variables here because we call the "getLocsForFP" memeber
    // function; which uses the class's Dbt and cursor variables 
    Dbt         dbFindKey;
    Dbt         dbStoredValue;
    HashValue_t next_key;
	Dbc        *localdbc;
try
    {

        // open a local cursor
        dbh_.cursor(NULL, &localdbc, 0);

        //clear the database value variables
        memset(&dbStoredValue, 0, sizeof(dbStoredValue));
        memset(&dbFindKey, 0, sizeof(dbFindKey));
        memset(&next_key, 0, sizeof(HashValue_t));

        // set the sizes for the value
        dbStoredValue.set_size(sizeof(FilePosition_t));
        dbFindKey.set_size(sizeof(HashValue_t));

        //set the key to find
        dbFindKey.set_data((void*)(&fromKey));
        memcpy(&next_key,dbFindKey.get_data(),sizeof(HashValue_t));

        int ret;
        // set the flag so the cursor's get will find the smallest key that is
        // greater-than-or equal to lower limit specified by the 'fromKey' parameter
        u_int32_t getFlag = DB_SET_RANGE;

        // Loop through the unique key values until reaching the upper limit
        while ((ret = localdbc->get(&dbFindKey, &dbStoredValue, getFlag)) == 0)
        {
            memcpy(&next_key,dbFindKey.get_data(),sizeof(HashValue_t));
            // make sure the found key is less-than-or-equal to the upper limit
            // specified by the 'toKey' parameter
            if (next_key <= toKey)
            {
                getLocsForFP(next_key, pLocationVector);
            }
            else
                break;
            // reset the flag so the cursor's get will find the next nonduplicate key
            getFlag = DB_NEXT_NODUP;
       }

        //close our local cursor
        localdbc->close();

    }
    // DbException is not a subclass of std::exception, so we
    // need to catch them both.
    catch(DbException &e)
    {
        std::cerr << "Error opening database cursor for: " << dbFileName_ << "\n";
        std::cerr << e.what() << std::endl;
    }
    catch(std::exception &e)
    {
        std::cerr << "OS Error opening cursor for: " << dbFileName_ << "\n";
        std::cerr << e.what() << std::endl;
    }
    return 0;
}

int TextFPLocationBDB::getLocsForPartialFP(HashValue_t pStartFP, std::vector<FilePosition_t> &pLocationVector)
{
    // set a default return value
    int returnValue         = 0;
    // later we check to ensure the length difference is in the proper range
    int patLengthDiff       = winLength_ - lenOfShortPattern_;
    // we need these values to calculate the maximum allowable difference
    // between the window length used to buiild the original index and the 
    // length of the pattern we are now using to calculate the range
    double logb2ofRadix     = log((double) radix_)/log(2.0);
    double logb2ofModulus   = log((double) modulo_)/log(2.0);

    int maxAllowableDiff    = (int)(logb2ofModulus/logb2ofRadix);

    // make sure the difference in pattern lengths is small enough to give us a range 
    // of fingerprints that are usable to search for locations
    if (maxAllowableDiff < patLengthDiff)
    {
        std::cout << "Pattern is too long.. Max leng for radix & q is: " << maxAllowableDiff << "\n";
        returnValue = -1;
    }
    else
    {
        // calculate the amout we need to shift the pattern's fingerprint
//HashValue_t shiftMultiplier = modpower(radix_, patLengthDiff, modulo_);
HashValue_t shiftMultiplier = modradpow64(radix_, patLengthDiff, modulo_);
        // calculate the lower bound by shifting the fingerprint
        HashValue_t fromKey         = modmult64(pStartFP, shiftMultiplier, modulo_);
        // calculate the upper bound amount by substracting one from the shift amount
        shiftMultiplier             = modadd(shiftMultiplier, - 1 , modulo_);
        // now we add the upper bound amount to the from fingerprint
        HashValue_t toKey           = modadd(fromKey, shiftMultiplier , modulo_);
//cout << " shift: " << shiftMultiplier  << "\n";
//cout << " from key: " << fromKey << " toKey: " << toKey << " lengthdif " << patLengthDiff << "\n";
//getc(stdin);
        // fill the location vector with the locations associated with the range of fingerprints
        getLocsForFPRange(fromKey, toKey, pLocationVector);
    }

    return returnValue;
}

void TextFPLocationBDB::showLocsInVector(std::vector<FilePosition_t> &pLocationVector)
{
    std::vector<FilePosition_t>::iterator list_it;
    for(list_it = pLocationVector.begin(); list_it!=pLocationVector.end(); list_it++)
    {
        std::cout << *list_it << "\n";
    }
    return;
}

void TextFPLocationBDB::sortLocsInVector(std::vector<FilePosition_t> &pLocationVector)
{
    std::sort(pLocationVector.begin(), pLocationVector.end());
    return;
}

int TextFPLocationBDB::getLocsForPattern(std::vector<FilePosition_t> &pLocationVector)
{
    int returnValue         = 0;
    
    if (sPatternLength_ == winLength_)
    {
        getLocsForFP(sPatternFPs_[0], pLocationVector);
        returnValue = pLocationVector.size();
    }

    else if (sPatternLength_ < winLength_)
    {
        if (getLocsForPartialFP(sPatternFPs_[0], pLocationVector) >= 0)
        {
            returnValue = pLocationVector.size();
//cout << " get locs: " <<  returnValue << "\n";
            sortLocsInVector(pLocationVector);
        }
        else
            returnValue = -1;
    }

    else if (sPatternLength_ > winLength_)
    {
        //std::vector<HashValue_t> keysInPattern;
        std::vector<HashValue_t>::size_type vec_it=0;

        // set the flag telling us we need a partial match for the last pattern
        bool isLastPat_LT_win_length = false;
        if (lenOfShortPattern_ != winLength_) 
            isLastPat_LT_win_length = true;

        // create a vector iterator we can use to keep track of the locations associated
        // with the fingerprint for the first substring of the long search pattern
        std::vector<FilePosition_t>::iterator  locsForFirstPart_it;

        // create a vector object we can load with locations for the other substrings
        // in the search pattern (and a corresponding iterator object)
        std::vector<FilePosition_t>            locsForNextParts;
        std::vector<FilePosition_t>::iterator  locsForNextParts_it;
        
        // declare a variable for the offset of the next key's location
        FilePosition_t nextKeyOffset = 0;

        // assign the first key's value
        HashValue_t key = sPatternFPs_[0];

        // fill location vector with the file positions associated with the fingerprint 
        // for the first substring of the long search pattern
        getLocsForFP(key, pLocationVector);

        // now we loop through the remaining substrings of the search pattern to see if their
        // locations match up with the locations for the first part of the pattern.  That is,
        // if their position is the correct offset from the first pattern's position.
        for (vec_it = 1; vec_it < sPatternFPs_.size(); vec_it++)
        {
            // make sure our vector object is empty because we are in a loop and we are finished
            // with the locations for the previous substring
            locsForNextParts.clear();
            // get the next fingerprint from our search pattern key vector
            key = sPatternFPs_[vec_it];
            // check to see if we are on the last substring AND that it is a short pattern key
            if (vec_it == (sPatternFPs_.size()-1) && isLastPat_LT_win_length)
            {   // If we get into this part of the "if" statement, then the last substring in 
                // search pattern is shorter than the index's window length; meaning we must 
                // calculate a 'from' & 'to' key
                int returnValue1 = getLocsForPartialFP(key, locsForNextParts);

                // ****------- IF RETURNVALUE < 0 THE OPERATION FAILED BECAUSE THE MAXDIFF WAS EXCEEDED --------****
            }
            else
            {
                // fill the vector with locations for the next key in the pattern
                getLocsForFP(key, locsForNextParts);
            }

            // reset the first substring's location vector iterator back at the beginning 
            locsForFirstPart_it = pLocationVector.begin();
            // loop through the locations from the first substring's fingerprint looking for corresponding
            // locations for the next keys
            while (locsForFirstPart_it != pLocationVector.end())
            {
                // calculate the file position from the start of the search pattern to the start of this substring
                nextKeyOffset = *locsForFirstPart_it + (winLength_ * vec_it);
                // look for this location in the vector of locations for this substring
                locsForNextParts_it = find(locsForNextParts.begin(), locsForNextParts.end(), nextKeyOffset);
                // not finding this location in the vector means that this substring does not occur in the file at
                // the corresponding offset; which means that the location for the first substring cannot be a 
                // candidate for the search pattern occurring at that location, so we delete it.  In other words, 
                // since the current substring's fingerprint occur at the offset from the first key's location, the
                // entire search pattern can't exist there.  However, if we do find that this substring does occur 
                // at the corresponding locations, then this location is still a candidate.  So, we keep it and go 
                // on to check the next location for the first substring.
                if (locsForNextParts_it == locsForNextParts.end())
                {
                    locsForFirstPart_it = pLocationVector.erase(locsForFirstPart_it);
                }
                else // since the locations correspond, we skip to the next location by advancing the iterator
                {
                    locsForFirstPart_it++;
                }
                
            }; // end of looping through the first substring's locations 
        } // end of looping through the subsequent substrings in the search pattern.

        // the first substring's vector of locations now contains only those locations that have 
        // corresponing fingerprints from the rest of the pattern at the proper offset from these
        sortLocsInVector(pLocationVector);
        returnValue = pLocationVector.size();
    }
    else
    {
        returnValue = -1;
    } // end of the composite if statement checking the length of the search pattern with the window length

    return returnValue; // a negative return value indicates no locations were found due to a complication
                        // such as the last substring being too long for this radix and modulo to produce
                        // meaningful fingerprint ranges.
}

void TextFPLocationBDB::setParameters(HashValue_t radix, HashValue_t q, int winLength, std::string &txtFileName, FILE *txtFile)
{
    radix_       = radix;
    modulo_      = q;
    winLength_   = winLength;
    txtFileName_ = txtFileName;
    txtFile_     = txtFile;
    return;
}

void TextFPLocationBDB::setPattern(const char* pPat)
{
    // set/initialize the basic pattern member variables
    searchPattern_      = pPat;
    sPatternLength_     = strlen(pPat);
    numKeysInPattern_   = 1;
    lenOfShortPattern_  = sPatternLength_;
//cout<< "pat: " << pPat << " length: " << sPatternLength_<< "\n";
    // empty the fingerprint vector so we can fill it with fresh values
    sPatternFPs_.clear();

    // we use this local vairiable to place the fingerprints into the vector
    HashValue_t keyToAdd;

    // we need to populate the fingerprint vector with the search pattern's fingerprints
    if (sPatternLength_ < winLength_)
    {
        // calculate the fingerprint of the short pattern; which we will use later
        // when calculating the range of values
        keyToAdd = hash_value(pPat, 0, sPatternLength_, radix_, modulo_);
//cout<< "Key: " << keyToAdd << "\n";
        sPatternFPs_.push_back(keyToAdd);
    }
    else if (sPatternLength_ == winLength_)
    {
        keyToAdd = hash_value(pPat, 0, sPatternLength_, radix_, modulo_);
        sPatternFPs_.push_back(keyToAdd);
    }
    else if (sPatternLength_ > winLength_)
    {
        int fromPos = 0;
        int toPos   = winLength_;

        // divide the search pattern into chunks the size of win_length and 
        // calculate the has values for those chunks
        while (fromPos < sPatternLength_)
        {
            keyToAdd = hash_value(pPat, fromPos, toPos, radix_, modulo_);
            sPatternFPs_.push_back(keyToAdd);
            lenOfShortPattern_ = toPos-fromPos;
            fromPos += winLength_;
            toPos    = min(fromPos + winLength_, sPatternLength_);
        };

    }
    else
    {
        numKeysInPattern_ = 0;
        lenOfShortPattern_ = -1;
    };
    
    return;
}

// this function verifies the locations by going to the position in the text file and checking
// each character from that location forward against the corresponding characters in the 
// current search pattern. It returns the number of spurious hits (i.e., positions where
// the individual characters do not match.)  It also removes these locations from the 
// location vector so it is with only those locations where the characters match.
int TextFPLocationBDB::getMatchesInTextFile(std::vector<FilePosition_t> &pLocationVector)
{
   
    int     sPatternIndex   = 0;
    int     numSpuriousHits = 0;
    bool    isSpuriousHit   = false;
    char    fileChar;
    // fpos_t is a type needed to position the file pointer to a particular location
    // we initialize it to zero and move the pointer there to get everything started.
    fpos_t nextPosition(0);
    fsetpos(txtFile_,&nextPosition);

    // we will loop through the location vector one location at a time using this iterator
    std::vector<FilePosition_t>::iterator locVectorIterator = pLocationVector.begin();

    // we use a while statement so we can remove individual bad locations from the 
    // vector as we encounter them
    while (locVectorIterator < pLocationVector.end())
    {
        // we set the file position variable to the current location by type casting the 
        // location vector iterator and we move the pointer to that location
        nextPosition = (fpos_t)(*locVectorIterator);
        fsetpos(txtFile_,&nextPosition);
        
        // initialize our flag that tells us that a file position is a spurious hit
        isSpuriousHit = false;

        // initialize the search pattern character index to the beginning of the string
        sPatternIndex = 0;

        // loop through each character in the search pattern
        while (sPatternIndex < sPatternLength_)
        {
            // read the character from the text file and advance the pointer one position
            fileChar = getc(txtFile_);
//cout << "/n File : " << fileChar << " Pat : " << searchPattern_[sPatternIndex];
//getc(stdin);
            // if the character from the text file does not match the correspodning character 
            // in the search pattern we will abandon the search and remove this file position 
            // from the location vector because we know it is a spurious hit.
            if (searchPattern_[sPatternIndex] != fileChar)
            {
                numSpuriousHits++;
                isSpuriousHit = true;
                break;
            }
            // move to the next character in the search pattern
            sPatternIndex++;
        
        } // end of looping through the characters in the search pattern

        // if we discovered a spurious hit we remove that element from the location vector ]
        // and leave the iterator to the next element that takes its place.
        if (isSpuriousHit)
            locVectorIterator = pLocationVector.erase(locVectorIterator);
        // otherwise, the current location is good and we move to the next element in the location vector
        else
            locVectorIterator++;

    } // end of looping through the elements of the location vector

    // return the number of spurious hits
    return numSpuriousHits;
}

void TextFPLocationBDB::writeResultsToFile(FILE * outFile, int pNumMatches, int pSpuriousHits)
{
    fprintf(outFile, "%d, %d, %d, %d, %lu, %lu\n", pNumMatches, pSpuriousHits, winLength_, sPatternLength_, radix_, modulo_);
}


